public class LeetCode10 {
    public boolean isMatch1(String s, String p) {
        if (isMatchPoint(s, p)){
            return true;
        }

        if (isMatchStar(s, p)){
            return true;
        }

        if (s.equals(p)){
            return true;
        }
        return false;
    }

    public boolean isMatchPoint(String s, String p){
        if (p.contains(".")){
            int index = p.indexOf('.');
            if (index != 0){
                String lastChar = p.substring(index - 1, index);
                System.out.println("lastChar:" + lastChar);

                if (s.contains(lastChar)){
                    return true;
                }else{
                    return false;
                }

            }
            return true;
        }

        return false;
    }

    public boolean isMatchStar(String s, String p){
        if (p.contains("*")){
            return true;
        }

        return false;
    }



    /*****************************************方法二-官方方法********************************************************************************/

    public boolean isMatch2(String s, String p) {
        int m = s.length();
        int n = p.length();

        boolean[][] f = new boolean[m + 1][n + 1];
        f[0][0] = true;
        for (int i = 0; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (p.charAt(j - 1) == '*') {
                    f[i][j] = f[i][j - 2];
                    if (matches(s, p, i, j - 1)) {
                        f[i][j] = f[i][j] || f[i - 1][j];
                    }
                } else {
                    if (matches(s, p, i, j)) {
                        f[i][j] = f[i - 1][j - 1];
                    }
                }
            }
        }
        return f[m][n];
    }

    public boolean matches(String s, String p, int i, int j) {
        if (i == 0) {
            return false;
        }
        if (p.charAt(j - 1) == '.') {
            return true;
        }
        return s.charAt(i - 1) == p.charAt(j - 1);
    }


    /*********************方法三**************************/
    public boolean isMatch(String s, String p) {

        char[] sChars = s.toCharArray();
        char[] pChars = p.toCharArray();

        int pIndex = 0;
        for (int i = 0; i < s.length(); ){
            if (pIndex >= p.length() ){
                return (p.contains("*")  || p.contains("."));
            }

            if (i == s.length() && pIndex == p.length()-1){
                return true;
            }

            if (i >= s.length()){
//                ){
                return false;
            }



            if (sChars[i] == pChars[pIndex]){
                i++;
                pIndex++;
                continue;
            }

            if (pChars[pIndex] == '*'){
                if (i > 0){
                    char lastChar = pChars[pIndex - 1];

                    if (lastChar == '.'){
                        i++;
                        pIndex++;
                        continue;
                    }

                    int sIndex = i - 1;
                    while (lastChar == sChars[sIndex]){
                        sIndex++;
                        if (sIndex >= s.length()){
                            break;
                        }
                    }

                    if (sIndex == s.length() && pIndex == p.length()-1){
                        return true;
                    }

                    i = sIndex;
                    pIndex++;

                    if (pIndex >= p.length()){
                        return false;
                    }

                    if (i >= s.length()){
                        return false;
                    }

                }else {
                    i++;
                    continue;
                }
            }

            if (pChars[pIndex] == '.'){

                if (pIndex == 0){
                    i++;
                    pIndex++;
                    continue;
                }

                if (sChars[i] == pChars[pIndex - 1]){
                    i++;
                    pIndex++;
                    continue;
                }

                return false;
            }

            return false;
        }



        return false;
    }

    /**
     * "mississippi"
     * "mis*is*p*."
     * 输出 true  预期 false
     *
     *
     * @param args
     */
    public static void main(String[] args) {
        LeetCode10 leetCode10 = new LeetCode10();
        System.out.println("1:" + leetCode10.isMatch("aa","a"));
        System.out.println("2:" + leetCode10.isMatch("aa","a*"));
        System.out.println("3:" + leetCode10.isMatch("ab",".*"));
        System.out.println("4:" + leetCode10.isMatch("mississi","mis*is*i"));
    }
}
